#include <iostream>

using namespace std;

typedef long long LL;
LL a, m;
string s;
LL get_phi(LL x)
{
	LL ret = x;
	for (int i = 2; i <= x / i; i++)
	{
		if (x % i == 0)
		{
			ret = ret / i * (i - 1);
			while (x % i == 0) x /= i;
		}
	}
	if (x > 1) ret = ret / x * (x - 1);
	return ret;
}
LL get_b(string& s, LL phi)
{
	LL t = 0;
	bool flag = false;
	for (auto ch : s)
	{
		t = t * 10 + ch - '0';
		if (t >= phi)
		{
			flag = true;
			t %= phi;
		}
	}

	if (flag) t += phi;
	
	return t;
}
LL qpow(LL a, LL b, LL p)
{
	LL ret = 1;
	while (b)
	{
		if (b & 1) ret = ret * a % p;
		a = a * a % p;
		b >>= 1;
	}
	return ret;
}
int main()
{
	cin >> a >> m >> s;

	LL phi = get_phi(m);
	LL b = get_b(s, phi);

	cout << qpow(a, b, m) << endl;
	return 0;
}








